#include"heap.h"
//void HeapInit(Heap* php)
//{
//	assert(php);
//	php->size = 0;
//	php->capacity = 0;
//	php->data = NULL;
//}
//void HeapDestroy(Heap* php)
//{
//	assert(php);
//	free(php->data);
//	php->data = NULL;
//	php->size = 0;
//	php->capacity = 0;
//}
//void HeapPush(Heap* php, HPDataType x)
//{
//	assert(php);
//	if (php->size == php->capacity)
//	{
//		int newcapacity = php->capacity == 0 ? 4 : 2 * php->capacity;
//		HPDataType *tmp=(HPDataType*)realloc(php->data, sizeof(HPDataType) * newcapacity);
//		assert(tmp);
//		php->data = tmp;
//	}
//	php->data[php->size++] = x;
//	AdjustUp(php, php->size - 1, 0);
//}
//void AdjustUp(Heap* php, int end, int start)
//{
//	assert(php);
//	assert(end < php->size&& end>=0 && start >= 0&&start<php->size);
//	int child = end;
//	int parent = (child - 1) / 2;
//	while (child > start)
//	{
//		if (php->data[child] < php->data[parent])
//		{
//			swap(&php->data[child], &php->data[parent]);
//			child = parent;
//			parent = (child - 1) / 2;
//		}
//		else
//		{
//			break;
//		}
//	}
//}
//void swap(HPDataType* a1, HPDataType* a2)
//{
//	assert(a1 && a2);
//	HPDataType tmp = *a1;
//	*a1 = *a2;
//	*a2 = tmp;
//}
//void HeapPrint(Heap* php)
//{
//	assert(php);
//	for (int i = 0; i < php->size; i++)
//	{
//		printf("%d ", php->data[i]);
//	}
//	printf("\n");
//}
//void HeapPop(Heap* php)
//{
//	assert(php);
//	assert(php->size > 0);
//	swap(&php->data[0], &php->data[php->size - 1]);
//	php->size--;
//	if (php->size > 0)
//	{
//		AdjustDown(php, 0, php->size - 1);
//	}
//}
//void AdjustDown(Heap* php, int start, int end)
//{
//	assert(php);
//	assert(end < php->size&& end >= 0 && start >= 0 && start < php->size);
//	int parent = start;
//	int child = parent * 2 + 1;
//	while (child < php->size)
//	{
//		if (child + 1 < php->size && php->data[child] > php->data[child + 1])
//		{
//			child++;
//		}
//		if (php->data[parent] > php->data[child])
//		{
//			swap(&php->data[parent], &php->data[child]);
//			parent = child;
//			child = parent * 2 + 1;
//		}
//		else
//		{
//			break;
//		}
//	}
//}
//HPDataType HeapTop(Heap* php)
//{
//	assert(php);
//	assert(php->size > 0);
//	return php->data[0];
//}
//bool HeapEmpty(Heap* php)
//{
//	assert(php);
//	return php->size == 0;
//}
void swap(int* a1, int* a2)
{
	assert(a1 && a2);
	int tmp = *a1;
	*a1 = *a2;
	*a2 = tmp;
}
void HeapSort(int* arr,int sz)
{
	assert(arr);
	/*for (int i = 0; i < sz; i++)
	{
		AdjustUp(arr, i, 0);
	}*/
	for (int i = (sz - 1 - 1) / 2; i > 0; i--)
	{
		AdjustDown(arr, i, sz - 1);
	}
	int start = 0;
	int end = sz - 1;
	while (end > 0)
	{
		swap(&arr[end], &arr[start]);
		AdjustDown(arr, 0, end);
		end--;
	}

}
void AdjustDown(int* arr, int start, int end)
{
	assert(arr);
	int parent = start;
	int child = parent * 2 + 1;
	while (child < end)
	{
		if (child + 1 < end && arr[child] > arr[child+1])
		{
			child++;
		}
		if (arr[parent] > arr[child])
		{
			swap(&arr[parent], &arr[child]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
void AdjustUp(int* arr, int end, int start)
{
	assert(arr);
	int child = end;
	int parent = (child - 1) / 2;
	while (parent > 0)
	{
		if (arr[parent] > arr[child])
		{
			swap(&arr[parent], &arr[child]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}
void TopK(int* arr, int sz, int k)
{
	assert(arr);
	int* heapmin = (int*)malloc(sizeof(int) * k);
	for (int i = 0; i < k; i++)
	{
		heapmin[i] = arr[i];
	}
	for (int i = (k - 1 - 1) / 2; i >=0; i--)
	{
		AdjustDown(heapmin, i, k);
	}
	for (int i = k; i < sz; i++)
	{
		if (arr[i] > heapmin[0])
		{
			heapmin[0] = arr[i];
			AdjustDown(heapmin, 0, k );
		}
	}
	for (int j = 0; j < k; j++)
	{
		printf("%d ", heapmin[j]);
	}
	printf("\n");
	free(heapmin);
}